//
//  BinaryTree.cpp
//  leetcode
//
//  Created by Ellie on 2021/1/27.
//  Copyright © 2021 Ellie. All rights reserved.
//

#include <stdio.h>
#include "BinaryTree.h"
#include "Helper.h"

//
// BST Binary Search Tree
//
TreeNode* BinaryTreeBST::insertnode(TreeNode *root, int value)
{
    if(root == nullptr)
        return new TreeNode(value);
    if(value == root->val)
        return root;
    if(value > root->val)
        root->right = insertnode(root->right, value);
    else if(value < root->val)
        root->left = insertnode(root->left, value);
    return root;
}

TreeNode* BinaryTreeBST::findnode(TreeNode *root, int value)
{
    if(root == nullptr)
        return nullptr;
    if(value == root->val)
        return root;
    else if(value > root->val)
        return findnode(root->right, value);
    else if(value < root->val)
        return findnode(root->left, value);
    return root;
}

TreeNode* BinaryTreeBST::getmin(TreeNode* root)
{
    while (root->left != nullptr) {
        root = root->left;
    }
    return root;
}

TreeNode* BinaryTreeBST::getmax(TreeNode* root)
{
    while(root->right != nullptr)
        root = root->right;
    return root;
}

TreeNode* BinaryTreeBST::deletemin(TreeNode* root)
{
    if(root == nullptr)
        return nullptr;
    
    if(root->left == nullptr)
        return root->right;
    root->left = deletemin(root->left);
    return root;
}

TreeNode* BinaryTreeBST::deletemax(TreeNode* root)
{
    if(root == nullptr)
        return nullptr;
    if(root->right == nullptr)
        return root->left;
    root->right = deletemax(root);
    return root;
}

TreeNode* BinaryTreeBST::deletenode(TreeNode* root, int value)
{
    if(root == nullptr)
        return nullptr;
    if(value == root->val)
    {
        if(root->left == nullptr) return root->right;
        if(root->right == nullptr) return root->left;
        
        TreeNode* minnode = getmin(root->right);
        root->val = minnode->val;
        root->right = deletenode(root->right, root->val);
    }
    else if(value > root->val)
        root->left = deletenode(root->left, value);
    else
        root->right = deletenode(root->right, value);
    return root;
}

vector<TreeNode*> BinaryTreeBST::splitBST(TreeNode* root, int V)
{
    if(root == nullptr)
        return vector<TreeNode*>{nullptr, nullptr};
    if(root->val <= V)
    {
        auto splitright = splitBST(root->right, V);
        root->right = splitright[0];
        return { root, splitright[1] };
    }
    else
    {
        auto splitleft = splitBST(root->left, V);
        root->left = splitleft[1];
        return { splitleft[0], root };
    }
}

TreeNode* BinaryTreeBST::sortedListToBST(ListNode* head)
{
    return buildBSTHelper(head, nullptr);
}

// leetcode 109
// 1382. 将二叉搜索树变平衡
// right is null linklist end NULL
TreeNode* BinaryTreeBST::buildBSTHelper(ListNode* left, ListNode* right)
{
    if(left == right)
        return nullptr;
    ListNode* mid = getMedian(left, right);
    TreeNode* root = new TreeNode(mid->val);
    root->left = buildBSTHelper(left, mid);
    root->right = buildBSTHelper(mid->next, right);
    return root;
}

bool BinaryTreeBST::isSymmetric(TreeNode* left, TreeNode* right)
{
    if(left == nullptr && right == nullptr)
        return true;
    if(left == nullptr || right == nullptr)
        return false;
    bool same = left->val == right->val;
    return same && isSymmetric(left->left, right->right) && isSymmetric(left->right
                                                                        , right->left);
}


// 命名很容易出现错误的操作，left，right在下面的push过程中很容易造成错误，做好做区分,减少代码可能造成的低级错误
bool BinaryTreeBST::isSymmetricInteration(TreeNode* root1, TreeNode* root2)
{
    stack<TreeNode*> sk;
    sk.push(root1);
    sk.push(root2);
    while(!sk.empty())
    {
        TreeNode* leftnode = sk.top();
        sk.pop();
        TreeNode* rightnode = sk.top();
        sk.pop();
        
        if(leftnode == nullptr && rightnode == nullptr)
        {
            continue;
        }
        else if(leftnode == nullptr || rightnode == nullptr)
            return false;
        
        bool samevalue = leftnode->val == rightnode->val;
        if(!samevalue)
            return false;
        
        sk.push(leftnode->left);
        sk.push(rightnode->right);
        sk.push(leftnode->right);
        sk.push(rightnode->left);
    }
    return true;
}

string BinaryTreeBST::serialize(TreeNode* root)
{
    if(root == nullptr)
        return NULLNode + SEP;
    return to_string(root->val) + " " + serialize(root->left) + serialize(root->right);
}

TreeNode* BinaryTreeBST::deserialize(string data)
{
    stringstream ss(data);
    return deserializeHelper(ss);
}

TreeNode* BinaryTreeBST::deserializeHelper(stringstream& ss)
{
    string str;
    if(!(ss >> str) || str == NULLNode)
    {
        return nullptr;
    }
    int value = stoi(str);
    TreeNode* node = new TreeNode(value);
    node->left = deserializeHelper(ss);
    node->right = deserializeHelper(ss);
    return node;
}

vector<vector<int>> BinaryTreeBST::BSTSequences(TreeNode* root)
{
    if(root == nullptr)
        return {{}};
    deque<TreeNode*> que;
    vector<int> path;
    que.push_back(root);
    vector<vector<int>> result;
    doBSTSequences(result, que, path);
    return result;
}

void BinaryTreeBST::doBSTSequences(vector<vector<int>>& result, deque<TreeNode*> &inputqueue, vector<int>& path)
{
    if(inputqueue.empty())
    {
        result.push_back(path);
        printfVector("done one path", path);
        return;
    }
    
    Print_Nodes("doBSTSequences:", inputqueue);
    
    int n = inputqueue.size();
    while(n--)
    {
        Print_Nodes("while:", inputqueue);
        
        TreeNode* cur = inputqueue.front();
        inputqueue.pop_front();
        cout << "while get value:" << cur->val << endl;
        
        path.push_back(cur->val);
        
        int childcount = 0;
        if(cur->left != nullptr)
        {
            childcount ++;
            inputqueue.push_back(cur->left);
        }
        if(cur->right != nullptr)
        {
            childcount ++;
            inputqueue.push_back(cur->right);
        }
        doBSTSequences(result, inputqueue, path);
        
        Print_Nodes("before doBSTSequences:", inputqueue);
        while (childcount -- ) {
            inputqueue.pop_back();
        }
        Print_Nodes("after doBSTSequences:", inputqueue);
        inputqueue.push_back(cur);
        Print_Nodes("after after doBSTSequences:", inputqueue);
        cout << "cur:" << cur->val << endl << endl;
        path.pop_back();
    }
}

// 1,2,3
// sum = 0
// sum = sum * 10 + (1)每个位的数字
// 二进制一样的道理
int BinaryTreeBST::sumNumbers(TreeNode* root, int sum)
{
    if(root == nullptr)
        return 0;
    sum = sum * 10 + root->val;
    // sum = sum * 2 + root->val; 二进制转换成十进制
    if(root->left == nullptr && root->right == nullptr)
        return sum;
    else
    {
        return sumNumbers(root->left, sum) + sumNumbers(root->right, sum);
    }
}

// 二叉树的遍历
void BinaryTreeBST::pathSum(TreeNode* root, int targetSum, vector<vector<int>> &result)
{
    if(root == nullptr)
        return;
    int sum = targetSum - root->val;
    cachePath.push_back(root->val);
    if(sum == 0 && root->left == nullptr && root->right == nullptr)
    {
        // find one result
        result.push_back(cachePath);
    }
    pathSum(root->left, sum, result);
    pathSum(root->right, sum, result);
    cachePath.pop_back();
}

int BinaryTreeBST::pathSum(vector<int>& nums)
{
    // Hash表示[节点索引，值]，满二叉树的性质
    int size = nums.size();
    if(size == 0)
        return 0;
    
    // 创建一棵树，按照满二叉树的性质存放
    // 使用层序遍历计算路径的值
    // BFS, DFS
    
    unordered_map<int, int> treemap;
    for(int i=0;i<size;i++)
    {
        int numvalue = nums[i];
        int depth = numvalue / 100;
        int position = (numvalue - depth * 100) / 10;
        int value = numvalue % 100;
        
        int index = pow(2, depth - 1) + (position - 1);
        treemap[index] = value;
    }
    
    queue<pair<int, int>> qu;
    qu.push({1, treemap[1]});
    
    int retsum = 0;
    while (!qu.empty()) {
        pair<int, int> cur = qu.front();
        qu.pop();
        
        int left = cur.first * 2;
        int right = cur.first * 2 + 1;
        
        bool hasleft = (treemap.find(left) != treemap.end());
        bool hasright = (treemap.find(right) != treemap.end());
        
        if(!hasleft && !hasright)
        {
            retsum += cur.second;
        }
        
        if(hasleft)
        {
            qu.push({left, cur.second + treemap[left]});
        }
        if(hasright)
        {
            qu.push({right, cur.second + treemap[right]});
        }
    }
    return retsum;
}

int BinaryTreeBST::pathSum(TreeNode* root, int sum)
{
    if(root == nullptr)
        return 0;
    cacheIntResult = 0;
    inorderPathSum(root, sum);
    return cacheIntResult;
}

void BinaryTreeBST::inorderPathSum(TreeNode* root, int sum)
{
    if(root == nullptr)
        return;
    inorderPathSum(root->left, sum);
    pathSumRecursion(root, sum);
    inorderPathSum(root->right, sum);
}

void BinaryTreeBST::pathSumRecursion(TreeNode* root, int sum)
{
    if(root == nullptr)
        return;
    sum = sum -  root->val;
    if(sum == 0)
        cacheIntResult ++;
    pathSumRecursion(root->left, sum);
    pathSumRecursion(root->right, sum);
}

int BinaryTreeBST::longestUnivaluePath(TreeNode* root)
{
    cacheIntResult = 0;
    longestUnivaluePathRecursion(root);
    return cacheIntResult;
}

int BinaryTreeBST::longestUnivaluePathRecursion(TreeNode* root)
{
    if(root == nullptr)
        return 0;
    
    int left = longestUnivaluePathRecursion(root->left);
    int right = longestUnivaluePathRecursion(root->right);
    
    int retleft = 0;
    int retright = 0;
    
    if(root->left != nullptr && (root->left)->val == root->val)
    {
        retleft = left + 1;
    }
    
    if(root->right != nullptr && (root->right)->val == root->val)
    {
        retright = right + 1;
    }
    cacheIntResult = max(cacheIntResult, retright + retleft);
    // 返回最大长度的那个节点值
    return max(retright, retleft);
}

int BinaryTreeBST::maxPathSum(TreeNode* root)
{
    cacheIntResult = INT_MIN;
    return 0;
}

int BinaryTreeBST::maxPathSumPostOrder(TreeNode* root)
{
    if(root == nullptr)
        return 0;
    int leftvalue = maxPathSumPostOrder(root->left);
    int rightvalue = maxPathSumPostOrder(root->right);
    
    int checkleftvalue = root->val + leftvalue;
    int checkrightvalue = root->val + rightvalue;
    int checkall = root->val + leftvalue + rightvalue;
    int checkroot = root->val;
    
    // 保存中间的逻辑计算结果
    int curmax = max(checkleftvalue, max(checkrightvalue, max(checkall, checkroot)));
    cacheIntResult = max(cacheIntResult, curmax);
    // 返回正确的路径，左右子树都返回sum最大值情况
    // right+root
    // left+root
    // root
    return max(checkleftvalue, max(checkroot, checkrightvalue));
}

// 求解完全二叉树的节点个数
// 满二叉树的节点个数为pow(2,n) - 1
// logN*LogN 一颗完全二叉树至少有一个子树为完全二叉树
int BinaryTreeBST::countNodes(TreeNode* root)
{
    if(root == nullptr)
        return 0;
    TreeNode* lefttree = root;
    TreeNode* righttree = root;
    int leftheight = 0;
    int rightheight = 0;
    
    while(lefttree != nullptr)
    {
        lefttree = lefttree->left;
        leftheight ++;
    }
    
    while(righttree != nullptr)
    {
        righttree = righttree->right;
        rightheight ++;
    }
    if(rightheight == leftheight)
        return pow(2, rightheight) - 1;
    else
        return 1 + countNodes(root->left) + countNodes(root->right);
}

int BinaryTreeBST::diameterOfBinaryTree(TreeNode* root)
{
    cacheIntResult = 0;
    diameterOfBinaryTreeRecursion(root);
    return cacheIntResult;
}

int BinaryTreeBST::diameterOfBinaryTreeRecursion(TreeNode* root)
{
    if(root == nullptr)
        return 0;
    int left = diameterOfBinaryTreeRecursion(root->left);
    int right = diameterOfBinaryTreeRecursion(root->right);
    
    cacheIntResult = max(cacheIntResult, left + right);
    return max(left, right) + 1;
}
